package com.jhy.suixianglu.daima20230116;

public class StrStr {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        // 先求出我们的next数组下标的值 也就是初始化
        int[] next = new int[needle.length()];
        // 给next赋值
        getNext(next, needle);
        // 定义一个j来记录我们next数组的下标
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return i - needle.length() + 1;
            }
        }
        return -1;

    }

    private void getNext(int[] next, String needle) {
        // 定义前缀的末尾
        int pre = 0;
        // 首尾的最长公共前缀始终为0
        next[pre] = 0;
        for (int suf = 1; suf < needle.length(); suf++) {
            // 前后缀不相等的情况
            while (pre > 0 && needle.charAt(pre) != needle.charAt(suf)) {
                pre = next[pre - 1];
            }
            // 相等的情况
            if (needle.charAt(pre) == needle.charAt(suf)) {
                pre++;
            }
            // 更新next数组
            next[suf] = pre;
        }
    }
}
